package com.chapter2.sort;

/** 
 * @ClassName: HeapSort 
 * @Description: 堆排序
 * 
 * 实现思路，构建堆数组，然后逐个取出数组第一个项（最大值），并放到末尾位置
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-17 下午8:36:55 
 *  
 *  
 * TODO 没有完全实现
 */
@Deprecated
public class HeapSort extends AbstractSort{

	@Override
	public void sort(int[] a) {
		int len=a.length;
		
		for(int i=(len-1)/2;i>0;i--){
			swiftDown(a,i,len);
		}
		
		while(len>0){
			exchange(a, 0, --len);
			swiftDown(a, 1, len);
		}
	}

	/** 
	* @Title: swiftDown 
	* @Description: 下沉
	* @param @param a
	* @param @param i    设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	private void swiftDown(int[] a, int i,int len) {
		while(i*2<len-1){
			int j=i*2;
			if(less(a[j], a[j+1])) j++;
			if(less(a[j], a[i])) break;
			exchange(a, i, j);
		}
	}
	
}
